The present invention relates to a neural network system, and in particular, to a neural network system capable of determining an optimal solution to a problem at a high speed.
Heretofore, a neural network, handling an optimization Problem has been described in "`Neural` Computation of Decisions in Optimization Problems", Biological Cybernetics, 52, (1986), pp. 141-152 (to be referred to as reference 1 herebelow). In reference 1, a method of determining a local minimum has been described. Moreover, as a method of determining an optimal solution, there exists a simulated annealing method which has been described in "Optimization by simulated annealing", Science, 220, 4598 (1983), pp. 671-680 (to be referred to as reference 2 herebelow). A cooling schedule used by the simulated annealing method has been proposed in "Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images", IEEE, PAMI6 (1984), pp. 721-741 (to be referred to as reference 3 herebelow) and in "Optimal simulated-annealing method based on stochastic-dynamic programming", PHYSICAL REVIEW A, 5, 39 (1989), pp. 2635-2642 (to be referred to as reference 4 herebelow).
An application of a mean field approximation method to a spin glass system has been described in "Modeling Brain Function", Cambridge University Press, (1989) (to be referred to as reference 5 herebelow). An estimation of an optimal solution according to the simulated annealing method in a spin glass system has been proposed in "Cooling-Rate Dependence for the Spin-Glass Ground-State Energy: Implication for Optimization by Simulated Annealing", PHYSICAL REVIEW LETTERS, 11, 56 (1986), pp. 1148-1151 (to be referred to as reference 6 herebelow).
A technological formulation of a securities portfolio problem to be considered as an example of the application field has been formulated by "Portfolio Selection", Yale University, (1959) (to be referred to as reference 7 herebelow).
However, the neural network systems above have been attended with the following problems. In the conventional method of reference 1, when the energy state of the neural network is trapped in a local minimum depending on a distribution of the initial states of neurons, it is impossible for the energy state to escape therefrom. In order for the energy state of a neural network of a single interconnecting type to escape from the local minimum and to reach a global minimum, there is required an operation such as a tunnel effect for passing through an energy barrier. In reference 2, to overcome this problem, there has been devised a simulated annealing (SA) method in which a probability is introduced to the transition of the energy state of the network and the annealing is combined with the probability from analogy to physics.
In the simulated annealing method, the state transition in a direction in which the energy of the network increases is allowed on the basis of a probability q which depends on a temperature T(t) of the network. Owing to the fluctuation effect thus introduced to the network, the energy state can pass through the energy barrier. Moreover, when the network temperature T(t) is lowered to gradually decrease the probability q, the energy state of the network can reach a global minimum without being captured by a local minimum. Namely, the energy state can be converged thereto. A representative cooling schedule has been proposed by S. Geman et al. in reference 4 as follows. ##EQU1## In the neural network system adopting the simulated annealing method, although the network can escape from the energy state, as a local minimum, there has been a problem that a long period of time is required for the computation. Furthermore, in both above systems, it has not been guaranteed that constraints are satisfied in any situations.
The spin glass system described in reference 5 is an alloy system in which a small amount of magnetic atoms (for example, iron atoms) are mixed with non-ferromagnetic metal (for example, copper). In this alloy system, the axis of the spin of each electron of the atoms may be oriented to either one of the directions related to the ferromagnetism and diamagnetism, respectively. Consequently, the respective electrons interact with each other with a nonuniform force therebetween and the energy state of the spin glass system may take many local minima. When there exist many local minima, it is difficult to obtain the global minimum, namely, the optimal solution. Therefore, based on a solution to a problem of the spin glass, the performance of the neural network system can be judged. In a neural network system in which the mean field approximation method is applied to the spin glass system, the optimal solution is only estimated, and, it is not guaranteed that the optimal solution is obtained.
Attempts proposed to solve optimization problems with constraints by a neural network system of an interconnecting type are related to quadratic programmings in which an objective function can be represented in a quadratic form; moreover, in many cases, the attempts are associated with a 0-1 problem in which each variable is limited to take a binary value or either one of two values. Linear constraints are embedded in the objective function in the format in which the constraints are added thereto. In these methods of solution, there have existed the following problems. Namely, since the target of the optimization is minimization of the objective function, the constraints are not necessarily satisfied. Moreover, the solution is limited to discrete values.